Các định lý và tính chất Tô_màu_đồ

Các định lý và tính chất Tô_màu_đồ_thị

Các giá trị giới hạn của sắc số

Rõ ràng sắc số của một đồ thị sẽ không vượt quá số đỉnh của nó (bậc của đồ thị):

1 ≤ χ ( G ) ≤ n . {\displaystyle 1\leq \chi (G)\leq n.\,} .

Nếu G có clique kích thước k thì cần ít nhất k màu để tô màu đỉnh cho clique này (xem thêm bài về đồ thị đầy đủ), như vậy sắc số của một đồ thị sẽ không nhỏ hơn chỉ số clique của đồ thị đó:

χ ( G ) ≥ ω ( G ) . {\displaystyle \chi (G)\geq \omega (G).\,}

Nếu đồ thị đơn G có bậc cực đại bằng Δ(G) thì sắc số của nó không vượt quá Δ(G)+1[1].

Chứng minh

Gọi số đỉnh của G là n.Ta dùng Δ(G)+1 màu để tô n đỉnh của G như sau: xuất phát từ đỉnh thứ nhất đến đỉnh thứ n, tô màu đỉnh đầu tiên bằng 1 màu tùy ý trong Δ(G)+1 màu. Tô màu đỉnh kế tiếp bằng một màu khác với các màu đã tô cho các láng giềng của đỉnh đó. Việc tô màu này luôn thực hiện được, đến lượt 1 đỉnh bất kì, ta luôn có màu để tô cho nó, vì số màu Δ(G)+1 lớn hơn bậc của đỉnh bất kì.

Tổng quát hơn là định lý Brook, định lý khẳng định rằng:

Tất cả mọi đồ thị đơn và liên thông G, ngoại trừ đồ thị đầy đủ K n {\displaystyle K_{n}} và đồ thị chu trình bậc lẻ W n {\displaystyle W_{n}} , đều có sắc số nhỏ hơn hoặc bằng bậc cực đại: χ ( G ) ≤ {\displaystyle \chi (G)\leq } Δ(G).

Nếu đồ thị G có m cạnh thì sắc số của nó thỏa mãn:

χ ( G ) ( χ ( G ) − 1 ) ≤ 2 m . {\displaystyle \chi (G)(\chi (G)-1)\leq 2m.\,}

Chứng minh

Chứng minh quy nạp theo m (m là số tự nhiên) mệnh đề (*) sau:nếu đồ thị G có không quá m cạnh thì sắc số của nó thỏa mãn: χ ( G ) ( χ ( G ) − 1 ) ≤ 2 m . {\displaystyle \chi (G)(\chi (G)-1)\leq 2m.\,} Với m=0,1, mệnh đề (*) đúng.Giả sử mệnh đề (*) đúng đến m-1. Xét m.Gọi χ {\displaystyle \chi } là số tự nhiên lớn nhất thỏa mãn: χ ( χ − 1 ) ≤ 2 m . {\displaystyle \chi (\chi -1)\leq 2m.\,} Nếu bậc cực đại của G nhỏ hơn χ {\displaystyle \chi } thì như ta đã biết, sắc số của G không vượt quá bậc cực đại của nó cộng với một, nên sẽ không vượt quá χ {\displaystyle \chi } , suy ra luôn điều phải chứng minh.Nếu bậc cực đại của G lớn hơn hoặc bằng χ {\displaystyle \chi } , suy ra trong G tồn tại đỉnh a có deg(a) lớn hơn hoặc bằng χ {\displaystyle \chi } .Xóa đỉnh a và các cạnh liên thuộc của nó khỏi G ta nhận được đồ thị mới là G', đồ thị này có số cạnh thỏa mãn: m ′ = m − d e g ( a ) ≤ m − χ {\displaystyle m'=m-deg(a)\leq m-\chi } Theo giả thiết quy nạp, mệnh đề (*) đúng cho m' nên: χ ( G ′ ) ≤ 2 m ′ ≤ 2 ( m − χ ) {\displaystyle \chi (G')\leq 2m'\leq 2(m-\chi )} ,Suy ra: χ ( G ′ ) ≤ χ − 1 {\displaystyle \chi (G')\leq \chi -1} .Tức là sắc số của G' không thể vượt quá χ − 1 {\displaystyle \chi -1} , từ đó suy ra sắc số của G không vượt quá χ {\displaystyle \chi } . Như vậy mệnh đề cũng đúng với m.Suy ra mệnh đề (*) đúng với mọi m là số tự nhiên.

Một số định lý liên quan của sắc số

Định lý 1

Bất cứ chu trình độ dài lẻ nào cũng đều có sắc số bằng 3

Chứng minh:Giả sử chu trình có độ dài là 2 n + 1 {\displaystyle 2n+1} ta chứng minh theo số n {\displaystyle n}

n = 1 {\displaystyle n=1} chu trình gồm 3 đỉnh mà 2 đỉnh bất kì đều kề nhau ⇒ {\displaystyle \Rightarrow } dùng đúng 3 màu để tô
( n ) ⇒ ( n + 1 ) {\displaystyle (n)\Rightarrow (n+1)} Giả sử α {\displaystyle \alpha } là một chu trình có độ dài 2 ( n + 1 ) + 1 = 2 n + 3 {\displaystyle 2(n+1)+1=2n+3} với các dãy đỉnh là x 1 {\displaystyle x_{1}} , x 2 {\displaystyle x_{2}} ,..., x 2 n + 1 {\displaystyle x_{2n+1}} , x 2 n + 2 {\displaystyle x_{2n+2}} , x 2 n + 3 {\displaystyle x_{2n+3}} .

Nối x 1 {\displaystyle x_{1}} với x 2 n + 1 {\displaystyle x_{2n+1}} ta được một chu trình α {\displaystyle \alpha } 'có độ dài 2 n + 1 {\displaystyle 2n+1} .

Theo giả thuyết quy nạp chu trình α {\displaystyle \alpha } ' có sắc số bằng 3.

Lấy màu của x 1 {\displaystyle x_{1}} tô cho x 2 n + 2 {\displaystyle x_{2n+2}} còn màu của x 2 n + 1 {\displaystyle x_{2n+1}} tô cho x 2 n + 3 {\displaystyle x_{2n+3}} .

Chu trình α {\displaystyle \alpha } được tô màu mà không thêm màu mới vào.

Vậy chu trình α {\displaystyle \alpha } có sắc số bằng 3

Định lý 2

Đồ thị đầy đủ n đỉnh Kn có sắc số bằng n

Một số tiêu chuẩn đơn giản để kiểm tra xem 1 đồ thị có hai sắc số hay không:

Ta có định lý: Giả sử đồ thị G có ít nhất một cạnh. Đồ thị G có hai sắc số khi và chỉ khi G không có chu trình đơn vô hướng độ dài lẻ.

Chứng minh:

Giả sử G là đồ thị có hai sắc số. Theo Định lý 1 thì G không thể có chu trình đơn vô hướng độ dài lẻ.
Ngược lại giả sử G không có chu trình đơn vô hướng độ dài lẻ. Không mất tính tổng quát có thể xem G liên thông.

Chọn 1 đỉnh a nào đó bất kì trong đồ thị

Đặt m ( a ) = 0 {\displaystyle m(a)=0} (m: số màu)

Với x {\displaystyle x} ≠ {\displaystyle \neq } a {\displaystyle a} Ta ký hiệu d ( x ) {\displaystyle d(x)} là độ dài đường đi vô hướng ngắn nhất nối a {\displaystyle a} với x {\displaystyle x}

Đặt m ( x ) = d ( x ) {\displaystyle m(x)=d(x)} mod 2

Ta sẽ chứng minh m là hàm màu của G

Giả sử x , y {\displaystyle x,y} kề nhau

Lấy d ( x ) {\displaystyle d(x)} là đường đi vô hướng ngắn nhất nối a với x có độ dài d ( x ) {\displaystyle d(x)} d ( y ) {\displaystyle d(y)} là đường đi vô hướng ngắn nhất nối a {\displaystyle a} với y {\displaystyle y} có độ dài d ( y ) {\displaystyle d(y)}

Chu trình đơn [ d ( x ) , ( x , y ) , d ( y ) ] {\displaystyle [d(x),(x,y),d(y)]} có độ dài d ( x ) + d ( y ) + 1 {\displaystyle d(x)+d(y)+1} phải là một số chẵn

Vậy thì d ( x ) + d ( y ) {\displaystyle d(x)+d(y)} là một số lẻ ⇒ {\displaystyle \Rightarrow } d ( x ) , d ( y ) {\displaystyle d(x),d(y)} khác nhau tính chẵn lẻ

⇒ {\displaystyle \Rightarrow } m ( x ) {\displaystyle m(x)} ≠ {\displaystyle \neq } m ( y ) {\displaystyle m(y)}

Hàm tô màu m có hai giá trị, vậy sắc số ≤ 2. G có ít nhất một cạnh nên sắc số của nó bằng 2

Từ định lý trên ta có hệ quả sau: Tất cả các chu trình độ dài chẵn đều có sắc số bằng 2.

Định lý 3

Ví dụ định lý 3: Tìm sắc số đồ thị

Phát biểu: Nếu G có chứa 1 đồ thị con đẳng cấu với Kn thì x ( G ) ≥ n {\displaystyle x(G)\geq n} .

Chứng minh: Hiển nhiên

Các giá trị giới hạn của số màu cạnh

Định lý 1

Số màu cạnh của đồ thị đơn G bất kì không vượt quá số đỉnh của nó.

Chứng minh

Xét đồ thị K n ′ {\displaystyle K'_{n}} có hai đỉnh bất kì liền kề và K n ′ {\displaystyle K'_{n}} có các khuyên. n là số đỉnh của K n ′ {\displaystyle K'_{n}} .

Đánh số các đỉnh của K n ′ {\displaystyle K'_{n}} là v 1 , v 2 , v 3 , … , v n {\displaystyle v_{1},v_{2},v_{3},\ldots ,v_{n}} .

Chỉ cần chứng minh K n ′ {\displaystyle K'_{n}} có thể tô màu các cạnh bởi n màu thì suy ra đồ thị đơn G bất kì có số đỉnh không vượt quá n đều có thể tô các cạnh bởi n màu.

Ký hiệu các màu là M 1 , M 2 , … , M n {\displaystyle M_{1},M_{2},\ldots ,M_{n}} .

Khi đó ta có cách tô màu cho K n ′ {\displaystyle K'_{n}} như sau.

Ma trận dưới đây biểu thị cách tô màu, trong đó:

giá trị ở hàng thứ i cột j chính là màu được gán cho cạnh ( v i , v j ) {\displaystyle (v_{i},v_{j})} ;

v 1 v 2 v 3 v 4 ⋯ v n − 2 v n − 1 v n v 1 M 1 M 2 M 3 M 4 ⋯ M n − 2 M n − 1 M n v 2 M 2 M 3 M 4 M 5 ⋯ M n − 1 M n M 1 v 3 M 3 M 4 M 5 M 6 ⋯ M n M 1 M 2 v 4 M 4 M 5 M 6 M 7 ⋯ M 1 M 2 M 3 ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ v n M n M 1 M 2 M 3 ⋯ M n − 3 M n − 2 M n − 1 . {\displaystyle {\begin{matrix}&v_{1}&v_{2}&v_{3}&v_{4}&\cdots &v_{n-2}&v_{n-1}&v_{n}\\v_{1}&M_{1}&M_{2}&M_{3}&M_{4}&\cdots &M_{n-2}&M_{n-1}&M_{n}\\v_{2}&M_{2}&M_{3}&M_{4}&M_{5}&\cdots &M_{n-1}&M_{n}&M_{1}\\v_{3}&M_{3}&M_{4}&M_{5}&M_{6}&\cdots &M_{n}&M_{1}&M_{2}\\v_{4}&M_{4}&M_{5}&M_{6}&M_{7}&\cdots &M_{1}&M_{2}&M_{3}\\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots &\vdots &\\v_{n}&M_{n}&M_{1}&M_{2}&M_{3}&\cdots &M_{n-3}&M_{n-2}&M_{n-1}\end{matrix}}.}

Định lý König khẳng định rằng đối với đồ thị hai phía G, số màu cạnh của nó bằng bậc cực đại của nó: χ ′ ( G ) = Δ ( G ) {\displaystyle \chi '(G)=\Delta (G)} .

Định lý Vizing khẳng định rằng, nếu đồ thị đơn G có bậc cực đại bằng Δ ( G ) {\displaystyle \Delta (G)} thì số màu cạnh của nó bằng Δ ( G ) {\displaystyle \Delta (G)} hoặc Δ ( G ) + 1 {\displaystyle \Delta (G)+1} .

Đa thức màu

Xem bài đa thức màu.